package com.ztom.v2;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author ZhangTao
 */
public class Code73LargestRectangleInHistograms {

    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }

        int max = 0;
        Deque<Integer> stack = new LinkedList<>();
        for (int i = 0; i < heights.length; i++) {
            while (!stack.isEmpty() && heights[stack.peekLast()] >= heights[i]) {
                Integer top = stack.pollLast();
                int lMin = stack.isEmpty() ? -1 : stack.peekLast();
                // i - lMin - 1 表示 (lMin, l) 中间夹着的区域的宽度
                max = Math.max(max, (i - lMin - 1) * heights[top]);
            }
            stack.addLast(i);
        }
        while (!stack.isEmpty()) {
            Integer top = stack.pollLast();
            int lMin = stack.isEmpty() ? -1 : stack.peekLast();
            // 右边没得小值
            int rMin = heights.length;
            max = Math.max(max, (rMin - lMin - 1) * heights[top]);
        }
        return max;
    }
}
